package com.future.algoriithm.dynamic.introduction;

/**
 * 动态规划思想入门
 * <p>
 * 动态规划是用来处理多阶段决策的最优问题
 * <p>
 * 多阶段决策问题：
 * 有一类活动的过程，可以分成若干个联系的阶段，在它的每一阶段都需要做出决策，从而使整个过程达到最好的活动效果
 * 当然，各个阶段的决策的选取不是任意确定的，它依赖于当前的状态，又会影响以后的发展。
 * 当各个阶段决策决定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。
 * 这样把一个问题看成是一个前后关联、具有链状结构的多阶段过程就称为多阶段决策过程，
 * 这种问题就称为多阶段决策问题。
 * <p>
 * 各个阶段采取的决策，一般来说是与阶段有关的。决策依赖于当前的状态，又随即引起状态的转移。
 * 一个决策序列就是在变化的状态中产生出来的。
 * 称这种解决多阶段决策最优化的过程为动态规划（DP）
 * <p>
 * 动态规划程序设计是解决最优化问题的一种途径，一种方法，而不是一种特殊算法。
 * 由于各种问题的性质不同，确定最优解的条件也互不相同，因此不存在一种万能的动态规划算法可以解决各类最优化问题。
 * <p>
 * 1、阶段和阶段变量：
 * 将问题的全过程恰当的分为若干个相互联系的阶段。
 * 阶段的划分一般根据时间和空间的自然特征去划分
 * 阶段的划分要便于把问题转化成多阶段决策问题。
 * 2、状态和状态变量
 * 通常一个阶段包含若干个状态，状态可由变量来描述。
 * 3、决策、决策变量和决策允许集合
 * 在对问题的处理中做出的每种选择性的行动就是决策。
 * 即从该阶段的每一个状态出发，通过一次选择性的行动转移至下一阶段的相应状态。
 * 一个实际问题可能需要有多次决策和多个决策点，在每一个阶段的每一个状态中都需要有一次决策，决策可以用变量来描述，称这种变量为决策变量。
 * 在实际问题中，决策变量的取值往往限制在某一个范围之内，此范围就称为决策允许范围。
 * 4、策略和最优策略
 * 所有阶段一次排列构成问题的全过程
 * 全过程中各阶段决策变量所组成的有序总体称为策略。
 * 在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略
 * 5、状态转移方程
 * 前一阶段的终点就是后一阶段的起点，对前一阶段的状体做出某种决策，就产生后一种阶段的状态，
 * 这种关系描述了从i阶段到i+1阶段状态的演变规律，称为状态转移方程。
 * <p>
 * 小结：动态规划问题的分析过程便是由五个部分组成：
 * 1、阶段 2、状态 3、决策 4、策略 5、状态转移方程
 * <p>
 * 什么样的"多阶段决策"问题适合用动态规划来求解
 * 必须满足两个条件：
 * 1、最优化原理：
 * 作为整个过程的最优策略，具有：
 * 无论过去的状态和策略如何，对前面的决策所形成的状态而言，余下的所有决策必须构成最优策略的性质。
 * 即：子问题的局部最优会形成整个问题的全局最优。
 * 即：问题具有最优子结构的性质。
 * 即：一个问题的最优解只取决于其子问题的最优解。
 * 2、无后效性原则：
 * 某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。
 * 也就是说，"未来与过去无关"。当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响未来的演变。
 * <p>
 * 小结：
 * 对于不能划分阶段的题，不能用动态规划来求解。
 * 不符合最优化原理，不能用动态规划来解。
 * 不具备无后效性原则的，不能用动态规划来解。
 * 误用动态规划解决问题会得到错误的结果！
 * <p>
 * 动态规划的设计方法：
 * 正推：从初始状态开始，通过对中间阶段的决策的选择，达到结束状态。我们也称递推。
 * 倒推：从结束状态开始，通过对中间阶段的决策的选择，达到开始状态。我们可以把这种方法看成记忆化搜索(搜索即递归)。
 *
 * @author jayzhou
 */
public interface Introduction {


    /**
     * POJ-1088 滑雪
     * Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，
     * 你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。
     * 区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
     * 1  2  3  4 5
     * 16 17 18 19 6
     * 15 24 25 20 7
     * 14 23 22 21 8
     * 13 12 11 10 9
     * 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。
     * 在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
     * Input
     * 输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
     * Output
     * 输出最长区域的长度。
     */
    public static int skiing() {
        return 0;
    }

    /**
     * 线性动态规划的一般求解思路：
     * f[i] 表示到第i个位置为止的最优解，f[i]怎么转移呢？
     * f[i] 一般从 f[j] 转移。f[j] 加上这一步转移所需要的代价。去更新 f[i]
     */
    void linearDynamicProgramming();

}




















